import random


def generateTestCase():
    n = random.randint(5, 10)
    nums = [random.randint(1, 10) for _ in range(n)]
    return n, nums


def way(n, nums):
    global cnt
    cnt = 0
    already = set()

    def dfs(start_index, count):
        global cnt
        if start_index == n:
            cnt = max(cnt, count)
            return
        # 选
        if nums[start_index] - 1 in already or nums[start_index] + 1 in already or nums[start_index] in already:
            ...
        else:
            already.add(nums[start_index])
            dfs(start_index + 1, count + 1)
            # if nums[start_index] in already:
            already.remove(nums[start_index])
        dfs(start_index + 1, count)

    dfs(0, 0)
    return cnt


def greedy(n, nums):
    nums = list(set(nums))
    nums.sort()
    length = len(nums)
    dp = [[0 for _ in range(2)] for _ in range(length)]
    dp[0][1] = 1
    for i in range(1, length):
        dp[i][0] = max(dp[i - 1])
        if nums[i] == nums[i - 1] + 1:
            dp[i][1] = dp[i - 1][0] + 1
        else:
            dp[i][1] = max(dp[i - 1]) + 1
    return max(dp[-1])


def main():
    n, nums = generateTestCase()
    ans_dp = greedy(n, nums)
    ans_dfs = way(n, nums)
    if ans_dp == ans_dfs:
        print(True)
    else:
        print(False)
        print(f"n={n}\nnums={nums}")
        print(f"ans_dp={ans_dp}")
        print(f"ans_dfs={ans_dfs}")


for i in range(500):
    main()
